package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202410;

public class leetcode20241001 {
    /**
     * 最低票价
     */
    public int mincostTickets(int[] days,int[] costs){
        int len=days.length;// 旅行的天
        int n=days[len-1];
        int[] dp=new int[n+1];// 记录哪些天去旅行
        int a,b,c;
        for(int i=0;i<len;i++){
            dp[days[i]]=1;
        }
        for(int i=1;i<=n;i++){
            if(dp[i]==0){
                dp[i]=dp[i-1];
            }else{
                a=dp[i-1]+costs[0];// 单天票
                if(i-7>=0){
                    b=dp[i-7]+costs[1];
                }else{
                    b=costs[1];
                }
                if(i-30>=0){
                    c=dp[i-30]+costs[2];
                }else{
                    c=costs[2];
                }
                dp[i]=Math.min(a,b);
                dp[i]=Math.min(dp[i],c);
            }
        }
        return dp[n];
    }
}
